CSE 311: Foundations of Computing I

CSE 311: Homework 5 Part 1

Due: Tuesday, May 19th by 6:00 PM

Instructions

Complete the problems on the following pages.

You are required to submit your own solutions. You are allowed to discuss the homework with other students. However, you must complete the problems in Grin on your own. Moreover, you must be able to explain your solution at any time. We reserve ourselves the right to ask you to explain your work at any time in the course of this class.

You have a total of three late days during the quarter, but you can only use one late day on any one homework, giving an additional day on both parts. Please plan ahead.

Submit your solution at http://grin.cs.washington.edu

  • Each part of each task is listed as its own problem.

  • You have unlimited attempts on each part.

  • All completed parts get full credit and uncompleted parts get no credit.

Task 1 – Grinning Regular Expressions

For each of the following, construct a regular expression that matches exactly the given set of strings.

  1. Binary strings that end with 00.

  2. Binary strings with an odd number of 1s.

    Hint: Think about what an arbitrary string in this language looks like around each of its 1s. Any number of 0s can appear before, between, and after the 1s.

  3. Binary strings that do not contain 00 as a substring.

    Hint: After every 0, what is allowed to come next?

Task 2 – Grinning Context-Free Grammars

For each of the following, construct a context-free grammar that generates exactly the given set of strings. The start symbol of your grammar should be 𝐒\mathbf{S}.

  1. Binary strings matching the regular expression “0(01∪10)*10(01 \cup 10)^* 1”.

  2. All strings of the form 0m12m+10^m 1^{2m+1}, where m∈ℕm \in \mathbb{N}.

  3. All strings of the form 0a1b0^a 1^b where b>a≥0b > a \ge 0.

Task 3 – Grinning Finite State Machines

For each of the following, construct a DFA that recognizes exactly the given language. For all states in your DFA, write “documentation” for them by describing, in English, the set of strings that end in that state. (No need to turn in the state documentation for this homework, but don’t skip it — you can and will be asked to write it on a quiz/exam with FSM problems.)

  1. Binary strings with an odd number of 0s.

  2. Binary strings that start with 1 and end with 0.

  3. Binary strings that contain 110 as a substring.